1. Field of the Invention
The present invention relates to computer architecture, in particular to deadlock avoidance in a computer system.
2. State of the Art
The PowerPC computer architecture, co-developed by Apple Computer, represents a departure from prior-generation small computer architectures. Prior-generation small computer architectures have generally been based on what is commonly known as a single-envelope bus. For a single-envelope bus, the address and data portions of the bus transaction are applied together during a given bus cycle. An example of a single-envelope bus is the PCI bus.
PowerPC machines currently sold by Apple are based largely on the Motorola MPC601 RISC microprocessor. Other related processors, including the MPC 604, MPC 603, MPC 603e, and MPC 602 are currently available and additional related processors including the MPC 620 will be readily available in the future. The MPC60x permits separate address bus tenures and data bus tenures, where tenure is defined as the period of bus mastership. In other words, rather than considering the system bus as an indivisible resource and arbitrating for access to the entire bus, the address and data buses are considered as separate resources, and arbitration for access to these two buses may be performed independently. A transaction, or complete exchange between two bus devices, is minimally comprised of an address tenure; one or more data tenures may also be involved in an exchange. There are two kinds of transactions: address/data and address-only.
A tenure, whether address or data, consists of three phases: arbitration, transfer, and termination. During address termination, a signal AACK.sub.-- occurs that marks the end of the address tenure and that is used to acknowledge the transfer of an address. During data termination, a signal TA.sub.-- occurs that marks the end of the data tenure and that is used to acknowledge the transfer of a data beat. A beat corresponds generally to a particular state of the address bus or the data bus. Transfers include both single-beat transfers, in which a single beat is transferred, and burst data transfers, in which a burst of four data beats is transferred.
Referring more particularly to FIG. 1, note that the address and data tenures are distinct from one another and that both consist of three phases--arbitration, transfer, and termination. FIG. 1 shows a data transfer that consists of a single-beat transfer (up to 64 bits). In a four-beat burst transfer, by contrast, data termination signals are required for each beat of data, but re-arbitration is not required. Having independent address and data tenures allows address pipelining (indicated in FIG. 1 by the fact that the data tenure begins before the address tenure ends) and split-bus transactions to be implemented at the system level in multi-processor systems. Address pipelining allows new address bus transactions to begin before the current data bus transaction has finished by overlapping the data bus tenure associated with a previous address bus tenure with one or more successive address tenures. Split-bus transaction capability allows the address bus and data bus to have different masters at the same time.
For clarity, the basic functions of address and data tenures will be discussed in somewhat greater detail.
In the case of address tenure, during address arbitration, address bus arbitration signals are used to gain mastership of the address bus. Assuming the CPU to be the bus master, it then transfers the address on the address bus during the address transfer phase. The address signals, together with certain transfer attribute signals discussed in greater detail hereinafter, control the address transfer. After the address transfer phase, the system uses the address termination phase to signal that the address tenure is complete or that it must be repeated.
In the case of data tenure, during address arbitration, the CPU arbitrates for mastership of the data bus. After the CPU is the bus master, during the data transfer phase, it samples the data bus for read operations or drives the data bus for write operations. Data termination signals occur in the data termination phase. Data termination signals are required after each data beat in a data transfer. In a single-beat-transaction, the data termination signals also indicates the end of the tenure, while in burst accesses, the data termination signals apply to individual beats and indicate the end of the tenure only after the final data beat.
Address-only transfers use only the address bus, with no data transfer involved. This feature is particularly useful in multi-master and multiprocessor environments, where external control of on-chip primary caches and TLB (translation look-aside buffer) entries is desirable. Additionally, the MPC60x provides a retry capability that supports an efficient "snooping" protocol for systems with multiple memory systems (including caches) that must remain coherent.
Pipelining and split-bus transactions, while they do not inherently reduce memory latency, can greatly improve effective bus-memory throughput. The MPC60x bus protocol does not constrain the maximum number of levels of pipe-lining that can occur on the bus between multiple masters. In a system in which multiple devices must compete for the system bus, external arbitration is required. The external arbiter must control the pipeline depth and synchronization between masters and slaves.
In a traditional pipelined implementation, data bus tenures are kept in strict order with respect to address tenures. However, external hardware can further decouple the address and data buses, allowing the data tenures to occur out of order with respect to the address tenures. Second-generation PowerPC computers include computers whose architecture was especially designed for high performance and that incorporated such hardware. This architecture supports true split-bus operation with ordered slaves and ordered masters. "Ordered" means each master and each slave has its own independent FIFO structure supporting "ordered" service to transactions posted to it. If a slave receives three transactions A, B, and C, then it will respond to A first, B second, and C third. If a master performs transactions D, E, and F, then it expects servicing of those transactions in the order of D first, E second, and F third. There can be up to some number of outstanding master/slave pair transactions in the architecture at one time. In an exemplary embodiment, there can be up to three outstanding master/slave pair transactions in the architecture at one time. As a result, in the foregoing architecture, a bridge, such as a video bridge, may concurrently have one outstanding slave transaction to it and one outstanding master transaction from it. Although ordered masters and slaves, as opposed to unordered masters and slaves, provide an overall simplification to system architecture, they can lead to deadlocks when there are conflicting completion dependencies.
Deadlock occurs in a system when one resource cannot complete an access to another resource, and the access blocks other resources from performing transactions on the bus. In the case of a bridge between a split bus and a single-envelope bus (such as the ARBus and the PCI bus), since the different buses are referenced to different clock signals of different frequencies and phases, transactions that pass from one side of the bus bridge to the other must pass an asynchronous boundary. An attempt to avoid deadlock by passing information across this boundary will lead to some uncertainty, such that not all deadlocks can be reliably avoided using such a technique.